package dynamic;

import java.util.*;

import org.junit.Test;


public class Ex300 {
    class Solution {

        //错误，看错题目
        public int lengthOfLIS_X(int[] nums) {
            //f[x]表示以x为底的自增序列
            int len = nums.length, res = 1;
            int[] f = new int[len];
            Arrays.fill(f, 1);

            for (int i = 1; i < len; i++) {
                f[i] = nums[i] > nums[i - 1] ? f[i - 1] + 1 : 1;
                res = Math.max(res, f[i]);
            }
            return res;
        }

        public int lengthOfLIS1(int[] nums) {
            //f[x]表示以x为底的自增子序列
            int len = nums.length, res = 1, max;
            int[] f = new int[len];
            Arrays.fill(f, 1);
    
            for (int i = 1; i < len; i++) {
                max = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] > nums[j]) max = Math.max(max, f[j]);
                }
                f[i] = max + 1;
                res = Math.max(res, f[i]);
            }
    
            return res;
        }

        //O(nlogn)解法，空间换时间
        //类似跳表思维，维护这样的一个二维数组 tail[][]：
        /* 
            以2,3,1,4
            2         1        1
            2 3  =>   1 3  =>  1  3
                               1  3  4

                    每一列保存同样的元素

            若nums[i] > tail[-1][-1], 直接拓展新的一层，并在最后位置增加一个nums[i]
            若nums[i] == tail[-1][-1], 或者在二维数组中存在num[i], 什么都不做
            若nums[i] < tail[-1][-1],找到数组中大于nums[i]的最小数对应的列，那个列全部改为nums[i]

            因为每一行是有序的，查找刚刚大于num[i]的位置使用二分，复杂度为o(logn)

            tail作为二维数组只是为了方便理解，实际上只需要最后一列，也省去了更新整个一列的O(n)行为
            最后tail长度为最终返回值，即最大升序子序列长度

            策略：贪心【使得递增幅度尽可能地小】
        */
        public int lengthOfLIS(int[] nums) {
            int len = nums.length, t, mid, lo, hi;
            List<Integer> tail = new ArrayList<>();
            tail.add(nums[0]);
            for (int i = 1; i < len; i++) {
                t = tail.get(tail.size() - 1);
                if (nums[i] > t) {
                    //比tail尾大，直接加到后面
                    tail.add(nums[i]);
                } else if (nums[i] < t) {
                    //比tail尾小，利用二分查找插入位置
                    lo = 0;
                    hi = tail.size() - 1;
                    while (lo < hi) {
                        mid = (hi - lo) / 2 + lo; //取中间靠左的位置
                        if (tail.get(mid) < nums[i]) {
                            lo = mid + 1;
                        } else {
                            hi = mid;
                        }
                    }
                    //跳出循环时，lo == hi, 有可能nums[lo] > nums[i], 也有可能相等。
                    //无论怎样，直接替换
                    tail.set(lo, nums[i]);
                } //else就是相等情况，可以直接跳过
            }

            //tail的长度就是最长递增子序列
            return tail.size();
        }
    
    }

    

    @Test
    public void test() {
        Solution s = new Solution();
        // int nums[] = {0,1,0,3,2,3};
        int nums[] = {10,9,2,5,3,7,101,18,4,8,6,12};
        // int[] nums = ArrayGenerator.getArray(100, 100);
        System.out.println(Arrays.toString(nums));
        int res = s.lengthOfLIS(nums);
        System.out.println(res);
    }
}
